Almost Cover-Free Codes and Designs

摘要

An $s$-subset of codewords of a binary code $X$ is said to be an {\em$(s,\ell)$-bad} in $X$ if the code $X$ contains a subset of other $\ell$codewords such that the conjunction of the $\ell$ codewords is covered by thedisjunctive sum of the $s$ codewords. Otherwise, the $s$-subset of codewords of$X$ is said to be an {\em $(s,\ell)$-good} in~$X$.mA binary code $X$ is said tobe a cover-free $(s,\ell)$-code if the code $X$ does not contain $(s,\ell)$-badsubsets. In this paper, we introduce a natural {\em probabilistic}generalization of cover-free $(s,\ell)$-codes, namely: a binary code is said tobe an almost cover-free $(s,\ell)$-code if {\em almost all} $s$-subsets of itscodewords are $(s,\ell)$-good. We discuss the concept of almost cover-free$(s,\ell)$-codes arising in combinatorial group testing problems connected withthe nonadaptive search of defective supersets (complexes). We develop a randomcoding method based on the ensemble of binary constant weight codes to obtainlower bounds on the capacity of such codes.